package chen_zhi_wei;

import org.w3c.dom.Node;

/**
 * @ClassName: CHEN_ZHI_WEI_23_Q2
 * @Author: WaterChen
 * @CreateTime: 2021/1/23 12:12
 * @Description: 链表实现队列
 */
public class CHEN_ZHI_WEI_23_Q2<T> {
    //记录首节点
    private Node head;
    //记录最后一个节点
    private Node last;
    //记录队列中元素的个数
    private int N;

    private class Node{
        public T item;
        public Node next;

        public Node(T item, Node next){
            this.item = item;
            this.next = next;
        }
    }
    //构造方法
    public CHEN_ZHI_WEI_23_Q2(){
        //默认不存储元素，不指向任何结点
        this.head = new Node(null,null);
        this.last = null;
        //默认情况下元素个数为0
        this.N=0;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //返回队列中元素的个数
    public int size(){
        return N;
    }

    //向队列中插入元素t
    public void enqueue(T t){
        if (last==null){
            //如果尾节点last为null，则让新结点指向尾节点
            last = new Node(t,null);
            //首节点指向尾结点
            head.next = last;
        }else{
            //如果尾结点last不为null
            //将新插入的结点设置为尾结点
            Node oldLast = last;
            last = new Node(t,null);
            //让旧的尾结点指向新的尾结点
            oldLast.next = last;
        }

        //元素个数加1
        N++;
    }

    //从队列中拿出一个元素
    public T dequeue(){
        //如果是空链表，直接返回空
        if (isEmpty()){
            return null;
        }

        Node oldFirst = head.next;
        //首节点指向旧的结点的下一个结点
        head.next = oldFirst.next;
        N--;

        //如果队列中的元素没有了，重置last=null
        if (isEmpty()){
            last=null;
        }

        return oldFirst.item;

    }


}
